package com.c2b.algorithm.leetcode.jzoffer;

/**
 * <a href="https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/description/">礼物的最大价值</a>
 * <p>在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
 * 给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？</p>
 * <pre>
 * 示例 1:
 *      输入:
 *      [
 *          [1,3,1],
 *          [1,5,1],
 *          [4,2,1]
 *      ]
 *      输出: 12
 * 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
 *
 *
 * 提示：
 *
 * 0 < grid.length <= 200
 * 0 < grid[0].length <= 200
 * </pre>
 *
 * @author c2b
 * @since 2023/4/6 17:16
 */
public class JzOffer0047MaxValue_M {

    public int maxValue(int[][] grid) {
        return dp(0, 0, grid);
    }

    private int dp(int row, int col, int[][] grid) {
        if (row == grid.length || col == grid[0].length) {
            return 0;
        }
        return grid[row][col] + Math.max(dp(row + 1, col, grid), dp(row, col + 1, grid));
    }

    public static void main(String[] args) {
        JzOffer0047MaxValue_M jzOffer0047MaxValue_m = new JzOffer0047MaxValue_M();
        int[][] ints = {
                {3,8,6,0,5,9,9,6,3,4,0,5,7,3,9,3},
                {0,9,2,5,5,4,9,1,4,6,9,5,6,7,3,2},
                {8,2,2,3,3,3,1,6,9,1,1,6,6,2,1,9},
                {1,3,6,9,9,5,0,3,4,9,1,0,9,6,2,7},
                {8,6,2,2,1,3,0,0,7,2,7,5,4,8,4,8},
                {4,1,9,5,8,9,9,2,0,2,5,1,8,7,0,9},
                {6,2,1,7,8,1,8,5,5,7,0,2,5,7,2,1},
                {8,1,7,6,2,8,1,2,2,6,4,0,5,4,1,3},
                {9,2,1,7,6,1,4,3,8,6,5,5,3,9,7,3},
                {0,6,0,2,4,3,7,6,1,3,8,6,9,0,0,8},
                {4,3,7,2,4,3,6,4,0,3,9,5,3,6,9,3},
                {2,1,8,8,4,5,6,5,8,7,3,7,7,5,8,3},
                {0,7,6,6,1,2,0,3,5,0,8,0,8,7,4,3},
                {0,4,3,4,9,0,1,9,7,7,8,6,4,6,9,5},
                {6,5,1,9,9,2,2,7,4,2,7,2,2,3,7,2},
                {7,1,9,6,1,2,7,0,9,6,6,4,4,5,1,0},
                {3,4,9,2,8,3,1,2,6,9,7,0,2,4,2,0},
                {5,1,8,8,4,6,8,5,2,4,1,6,2,2,9,7}
        };
        System.out.println(jzOffer0047MaxValue_m.maxValue(ints));
    }
}
